package LeetCode;

import com.company.Tree.Tree;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName DataStructure
 * @Description: TODO
 * @date ${DAT}10:25
 */
public class M8 {
    public static class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x;
      }
  }

    public static void main(String[] args) {
        TreeNode A = new TreeNode(1);
        A.left = new TreeNode(0);
        A.left.left = new TreeNode(-3);
        A.left.left.left = new TreeNode(-4);
        A.right = new TreeNode(1);
        TreeNode B = new TreeNode(1);
        B.left = new TreeNode(-4);
        System.out.println(new M8().isSubStructure(A,B));
    }

    public boolean isSubStructure(TreeNode A, TreeNode B) {
        boolean result = false;
        if (A!=null&&B!=null) {
            if (A.val == B.val) {
                result = CompearTo(A, B);
            }
            if (!result) {
                result = isSubStructure(A.left, B);//向左遍历
            }
            if (!result) {
                result = isSubStructure(A.right, B);
            }
        }
        return result;
    }
    public boolean CompearTo(TreeNode A,TreeNode B){
        if (B==null){
            return true;
        }
        if (A==null){
            return false;
        }
        if (!(A.val == B.val)){//只能是不等的判断不然进不了递归
            return false;
        }
        return CompearTo(A.left,B.left)&&CompearTo(A.right,B.right);
    }

}
